import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class Solution1268 {

    static class Trie {
        TreeSet<String> set=new TreeSet<>(String::compareTo);
        Trie[] children=new Trie[26];

        public void insert(String t) {
            Trie trie=this;
            for (char c : t.toCharArray()) {
                if (trie.children[c-'a']==null){
                    trie.children[c-'a']=new Trie();
                }
                trie=trie.children[c-'a'];
                trie.set.add(t);
            }
        }


    }

    public List<List<String>> suggestedProducts(String[] products, String searchWord) {
        List<List<String>> lists=new ArrayList<>();
        Trie trie=new Trie();
        for (String product : products) {
            trie.insert(product);
        }
        for (char c : searchWord.toCharArray()) {
            if (trie.children[c-'a']==null){
                trie.children[c-'a']=new Trie();
            }
            trie=trie.children[c-'a'];
            List<String> temp=new ArrayList<>();
            for (int i=0;i<3 && !trie.set.isEmpty();i++){
                String p=trie.set.first();
                trie.set.remove(p);
                temp.add(p);
            }
            lists.add(temp);
        }
        return lists;
    }

    public static void main(String[] args) {
        System.out.println(new Solution1268().suggestedProducts(new String[]{"mobile","mouse","moneypot","monitor","mousepad"},"mouse"));
    }
}
